﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace DFS
{
	TEST_CLASS(LC785)
	{
		//LC785. 判断二分图
		class Solution {
		public:
			bool isBipartite(vector<vector<int>>& graph) {
				m_vAns.resize(graph.size());
				m_vis.resize(graph.size());
				for (int i = 0; i < graph.size(); i++) {
					if (m_vAns[i] > 0) { continue; }
					m_vAns[i] = 1;
					DFS(i, graph);
				}
				return m_ans;
			}
			void DFS(int cur, vector<vector<int>>& graph) {
				if (m_vis[cur]) { return; }
				m_vis[cur] = true;
				for (const auto& next : graph[cur]) {
					const int iGroup = 3 - m_vAns[cur];
					if (iGroup + m_vAns[next] == 3) { m_ans = false; }
					m_vAns[next] = iGroup;
					DFS(next, graph);
				}
			}
			bool m_ans = true;
			vector<int> m_vAns;
			vector<bool> m_vis;
		};
	public:
		vector<vector<int>> graph;
		TEST_METHOD(TestMethod1)
		{
			graph = { {0},{2,3},{1,3},{1,2} };
			auto res = Solution().isBipartite(graph);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod11)
		{
			graph = { {1,2,3},{0,2},{0,1,3},{0,2} };
			auto res = Solution().isBipartite(graph);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod12)
		{
			graph = { {1,3},{0,2},{1,3},{0,2} };
			auto res = Solution().isBipartite(graph);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod13)
		{
			graph = { {},{2,4,6},{1,4,8,9},{7,8},{1,2,8,9},{6,9},{1,5,7,8,9},{3,6,9},{2,3,4,6,9},{2,4,5,6,7,8} };
			auto res = Solution().isBipartite(graph);
			AssertEx(false, res);
		}
	};

	TEST_CLASS(LC851)
	{
		//LC851. 喧闹和富有
		class Solution {
		public:
			vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
				m_quiet = quiet;
				m_ans.resize(quiet.size());
				m_vis.resize(quiet.size());
				iota(m_ans.begin(), m_ans.end(), 0);
				const int N = quiet.size();
				vector<vector<int>> neiBo(N);
				vector<int> outer(N);
				for (const auto& v : richer) {
					neiBo[v[1]].emplace_back(v[0]);
					outer[v[0]]++;
				}
				function<void(int)> DFS = [&](int cur) {
					if (m_vis[cur]) { return; }
					m_vis[cur] = true;
					for (const auto& next : neiBo[cur]) {
						DFS(next);
						if (m_quiet[next] < m_quiet[cur]) {
							m_quiet[cur] = m_quiet[next];
							m_ans[cur] = m_ans[next];
						}
					}
				};
				for (int i = 0; i < N; i++) {
					if (outer[i] > 0) { continue; }
					DFS(i);
				}
				return m_ans;
			}
			vector<int> m_quiet, m_ans, m_vis;
		};
	public:
		vector<vector<int>> richer;
		vector<int> quiet;
		TEST_METHOD(TestMethod11)
		{
			richer = { {1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3} }, quiet = { 3,2,5,4,6,1,7,0 };
			auto res = Solution().loudAndRich(richer, quiet);
			AssertEx(vector<int>{ 5, 5, 2, 5, 4, 5, 6, 7}, res);
		}
		TEST_METHOD(TestMethod12)
		{
			richer = {  }, quiet = { 0 };
			auto res = Solution().loudAndRich(richer, quiet);
			AssertEx(vector<int>{ 0}, res);
		}

	};

	TEST_CLASS(LC1600)
	{
		//LC1600. 王位继承顺序
		class ThroneInheritance {
		public:
			ThroneInheritance(string kingName) {
				Add(kingName);
			}

			void birth(string parentName, string childName) {
				Add(childName);
				m_vChilds[m_mNameToIndex[parentName]].emplace_back(m_mNameToIndex[childName]);
			}

			void death(string name) {
				m_death[m_mNameToIndex[name]] = true;
			}

			vector<string> getInheritanceOrder() {
				vector<string> ans;
				function<void(int)> DFS = [&](int cur) {
					if (!m_death[cur]) { ans.emplace_back(m_names[cur]); }
					for (const auto& child : m_vChilds[cur]) {
						DFS(child);
					}
				};
				DFS(0);
				return ans;
			}
			void Add(const string& name) {
				if (m_mNameToIndex.count(name)) { return; }
				m_names.emplace_back(name);
				m_mNameToIndex[name] = m_mNameToIndex.size();
				m_death.emplace_back(false);
				m_vChilds.emplace_back();
			}
			vector<string> m_names;
			unordered_map<string, int> m_mNameToIndex;
			vector<bool> m_death;
			vector<vector<int>> m_vChilds;
		};


	public:

		TEST_METHOD(TestMethod11)
		{
			ThroneInheritance t("king"); // 继承顺序：king
			t.birth("king", "andy"); // 继承顺序：king > andy
			t.birth("king", "bob"); // 继承顺序：king > andy > bob
			t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
			t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
			t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
			t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
			auto res = t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
			AssertEx(vector<string>{ "king", "andy", "matthew", "bob", "alex", "asha", "catherine" }, res);
			t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
			res = t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]
			AssertEx(vector<string>{"king", "andy", "matthew", "alex", "asha", "catherine" }, res);
		}


	};

	TEST_CLASS(LC2049)
	{
		//LC2049. 统计最高分的节点数目
		class Solution {
		public:
			int countHighestScoreNodes(vector<int>& parents) {
				const int N = parents.size();
				vector<vector<int>> vChild(N);
				for (int i = 0; i < N; i++) {
					if (-1 == parents[i]) { continue; }
					vChild[parents[i]].emplace_back(i);
				}
				vector<int> nodeCount(N, 1);
				function<void(int)> DFS = [&](int cur) {
					for (const auto& child : vChild[cur]) {
						DFS(child);
						nodeCount[cur] += nodeCount[child];
					}
				};
				DFS(0);
				map<long long, int> mCount;
				for (int i = 0; i < N; i++) {
					long long ans = 1;
					for (const auto& child : vChild[i]) {
						ans *= nodeCount[child];
					}
					ans *= max(1, N - nodeCount[i]);
					mCount[ans]++;
				}
				return mCount.rbegin()->second;
			}
		};
		vector<int> parents;

	public:

		TEST_METHOD(TestMethod11)
		{
			parents = { -1,2,0,2,0 };
			auto res = Solution().countHighestScoreNodes(parents);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			parents = { -1,2,0 };
			auto res = Solution().countHighestScoreNodes(parents);
			AssertEx(2, res);
		}
	};

	TEST_CLASS(LC2477)
	{
		//LC2477. 到达首都的最少油耗
		class Solution {
		public:
			long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
				auto neiBo = CNeiBo::Two(roads.size() + 1, roads, false);
				function < pair<int, long long>(int, int)> DFS = [&](int cur, int par) {
					int i1 = 1;
					long long i2 = 0;
					for (const auto& next : neiBo[cur]) {
						if (par == next) { continue; }
						auto [j1, j2] = DFS(next, cur);
						i1 += j1;
						i2 += j2 + (j1 / seats + (0 != (j1 % seats)));
					}
					return make_pair(i1, i2);
				};
				auto [i1, i2] = DFS(0, -1);
				return i2;
			}
		};

	public:
		vector<vector<int>> roads;
		int seats;
		TEST_METHOD(TestMethod11)
		{
			roads = { {0,1},{0,2},{0,3} }, seats = 5;
			auto res = Solution().minimumFuelCost(roads, seats);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			roads = { {3,1},{3,2},{1,0},{0,4},{0,5},{4,6} }, seats = 2;
			auto res = Solution().minimumFuelCost(roads, seats);
			AssertEx(7LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			roads = {}, seats = 1;
			auto res = Solution().minimumFuelCost(roads, seats);
			AssertEx(0LL, res);
		}
	};

	TEST_CLASS(LC3327)
	{
		//LC3327. 判断 DFS 字符串是否是回文串
		class Solution {
		public:
			vector<bool> findAnswer(vector<int>& parent, string s) {
				const int N = parent.size();
				int root = -1;
				m_childs.resize(N);
				for (int i = 0; i < N; i++) {
					if (-1 == parent[i]) { root = i; }
					else { m_childs[parent[i]].emplace_back(i); }
				}
				m_order1.resize(N);
				m_order2.resize(N);

				DFS(root);
				string str(N, ' ');
				for (int i = 0; i < N; i++) {
					str[m_order2[i]] = s[i];
				}
				CPalindrome pa;
				pa.CalCenterHalfLen(str);
				vector<bool> ans(N);
				for (int i = 0; i < N; i++) {
					const int left = m_order1[i];
					const int r = m_order2[i] + 1;
					const int len = r - left;
					const int halfLen = (len + 1) / 2;
					const int mid = (left + r + 1) / 2 - 1;
					if (len & 1) {
						ans[i] = pa.m_vOddCenterHalfLen[mid] >= halfLen;
					}
					else {
						ans[i] = pa.m_vEvenCenterHalfLen[mid] >= halfLen;
					}
				}
				return ans;
			}
			void DFS(int cur) {
				m_order1[cur] = m_iTime;
				for (const auto& child : m_childs[cur]) {
					DFS(child);
				}
				m_order2[cur] = m_iTime++;
			};
			vector<int> m_order1, m_order2;
			vector<vector<int>> m_childs;
			int m_iTime = 0;
		};
	public:
		vector<int> parent;
		string s;
		TEST_METHOD(TestMethod11)
		{
			parent = { -1,0,0,1,1,2 }, s = "aababa";
			auto res = Solution().findAnswer(parent, s);
			AssertEx({ true,true,false,true,true,true }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			parent = { -1,0,0,0,0 }, s = "aabcb";
			auto res = Solution().findAnswer(parent, s);
			AssertEx({ true,true,true,true,true }, res);
		}
	};

	TEST_CLASS(P5658)
	{
		//P5658 [CSP-S2019] 括号树
		class Solution {
		public:
			long long Ans(string s, vector<int>& parent) {
				const int N = s.length();
				parent.insert(parent.begin(), 0);
				for (auto& i : parent) {
					i--;
				}
				vector<vector<int>> childs(N);
				for (int i = 1; i < N; i++) {
					childs[parent[i]].emplace_back(i);
				}
				vector<long long> c(N), d(N);
				unordered_map<int, long long> mSuffVCnt;
				function<void(int, int)> DFS = [&](int cur, int iAdd) {
					const auto cvalue = ('(' == s[cur]) ? 1 : -1;
					iAdd += cvalue;
					mSuffVCnt[cvalue - iAdd]++;//s[cur...cur]数量+1
					auto cntErase = mSuffVCnt[-1 - iAdd];
					mSuffVCnt.erase(-1 - iAdd);//权值-1非法，删除
					c[cur] = mSuffVCnt[-iAdd];
					if (0 != cur) {
						d[cur] = d[parent[cur]];
					}
					d[cur] += c[cur];
					for (const auto& chi : childs[cur]) {
						DFS(chi, iAdd);
					}
					mSuffVCnt[-1 - iAdd] = cntErase;
					mSuffVCnt[cvalue - iAdd]--;
					iAdd -= cvalue;

				};
				DFS(0, 0);
				long long ans = 0;
				for (int i = 0; i < N; i++) {
					ans ^= (i + 1) * d[i];
				}
				return ans;
			}
		};
	public:
		vector<int> parent;
		string s;
		TEST_METHOD(TestMethod11)
		{
			parent = { 1,1,2,2 }, s = "(()()";
			auto res = Solution().Ans(s, parent);
			AssertEx(6LL, res);
		}

	};

	TEST_CLASS(B4189)
	{
		//【DFS序 树状数组】B4189 [中山市赛 2024] 树上开花|普及+		
		class Solution {
		public:
			long long Ans(vector<int>& a, vector<pair<int, int>>& edge) {
				const int N = a.size();
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				CDFSSort sort(neiBo, 0);
				vector<vector<int>> child(N);
				for (int i = 0; i < N; i++) {
					for (const auto& j : neiBo[i]) {
						if (sort.m_vSort[j] < sort.m_vSort[i]) { continue; }
						child[i].emplace_back(j);
					}
				}
				vector<vector<int>> v(N + 1);
				for (int i = 0; i < N; i++) {
					const int cur = sort.m_vNode[i];
					for (int j = 1; j * j <= a[cur]; j++) {
						if (0 != a[cur] % j) { continue; }
						v[j].emplace_back(i);
						const int j1 = a[cur] / j;
						if (j1 != j) { v[j1].emplace_back(i); }
					}
				}
				long long ans = 0;
				for (int i = 0; i < N; i++) {
					auto it1 = lower_bound(v[a[i]].begin(), v[a[i]].end(), sort.m_vSort[i]);
					auto it2 = lower_bound(v[a[i]].begin(), v[a[i]].end(), sort.m_vSort2[i]);
					ans += (long long)(it2 - it1) * (it2 - it1);
					for (const auto& son : child[i]) {
						auto it3 = lower_bound(v[a[i]].begin(), v[a[i]].end(), sort.m_vSort[son]);
						auto it4 = lower_bound(v[a[i]].begin(), v[a[i]].end(), sort.m_vSort2[son]);
						ans -= (long long)(it4 - it3) * (it4 - it3);
					}
				}
				return ans;
			}
		};
	public:
		vector<int>a;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			edge = { {1,2},{1,3},{2,4},{2,5} }, a = { 2,3,2,5,4 };
			auto res = Solution().Ans(a, edge);
			AssertEx(11LL, res);
		}
	};

	TEST_CLASS(P8779)
	{
		//【图论 前缀和】P8779 [蓝桥杯 2022 省 A] 推导部分和|普及+	
		class Solution {
		public:
			vector<long long> Ans(const int N, vector<tuple<int, int, long long>>& sum, vector<pair<int, int>>& que) {
				vector < vector<pair<int, long long>>> neiBo(N + 1);
				for (auto [left, r, s] : sum) {
					left--;
					neiBo[left].emplace_back(r, s);
					neiBo[r].emplace_back(left, -s);
				}

				vector<unordered_map<int, long long>> mPreSums(N + 1);
				vector<int> re(N + 1, -1);
				int region = -1;
				for (int i = 0; i <= N; i++) {
					if (-1 != re[i]) { continue; }
					region++;
					auto& mPreSum = mPreSums[region];
					function<void(int, long long)>  DFS = [&](int cur, long long w) {
						if (mPreSum.count(cur)) { return; }
						mPreSum[cur] = w;
						re[cur] = region;
						for (const auto& [next, w1] : neiBo[cur]) {
							DFS(next, w + w1);
						}
					};
					DFS(i, 0);
				}

				vector<long long> ans;
				for (auto [left, r] : que) {
					left--;
					const int g = re[left];
					if (g != re[r]) {
						ans.emplace_back(LLONG_MIN);
					}
					else {
						ans.emplace_back(mPreSums[g][r] - mPreSums[g][left]);
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<tuple<int, int, long long>> sum;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod11)
		{
			N = 5, sum = { {1,5,15},{4,5,9},{2,3,5} }, que = { {1,5},{1,3},{1,2} };
			auto res = Solution().Ans(N, sum, que);
			AssertEx({ 15,6,LLONG_MIN }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 4, sum = { {1,1,(long long)1e12},{2,2,(long long)1e12},{3,3,(long long)1e12},{4,4,(long long)1e12 } }, que = { {1,2}, {3,4} };
			auto res = Solution().Ans(N, sum, que);
			AssertEx({ (long long)2e12,(long long)2e12 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 3, sum = { {1,3,6},{2,3,5},{2,2,2} }, que = { {1,1}, {2,2},{3,3} };
			auto res = Solution().Ans(N, sum, que);
			AssertEx({ 1,2,3 }, res);
		}
	};

	TEST_CLASS(P8997)
	{
		//【DFS】P8997 [CEOI 2022] Homework|普及+
		class Solution {
		public:
			int Ans(const string& s) {
				int pos = 0;
				auto [tmp, iMin, iMax] = DFS(s, pos);
				return iMax - iMin + 1;
			}
			tuple<int, int, int> DFS(const string& s, int& i)
			{
				for (;; i++) {
					if ((',' == s[i]) || ('(' == s[i]) || (')' == s[i])) { continue; }
					if ('?' == s[i]) {
						i++;
						return { 1,0,0 };
					}
					if ('m' == s[i]) {
						const char ch2 = s[++i]; i += 2;
						auto [n1, m10, m20] = DFS(s, i);
						auto [n2, m11, m21] = DFS(s, i);
						if ('a' == ch2) {
							return { n1 + n2,(n1 + n2) - (n1 + n2 - m10 - m11 - 2) - 1,(n1 + n2) - min(n1 - m20 - 1, n2 - m21 - 1) - 1 };
						}
						else {
							return { n1+n2,min(m10,m11),m20 + m21 };
						}
					}
					else {
						assert(false);
					}
				}
			}

		};
	public:	
		TEST_METHOD(TestMethod11)
		{			
			auto res = Solution().Ans("min(?,?)");
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().Ans("max(?,?)");
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().Ans("max(?,min(?,?))");
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			auto res = Solution().Ans("max(?,max(?,min(?,?)))");
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod15)
		{
			auto res = Solution().Ans("min(max(?,?),min(?,max(?,?)))");
			AssertEx(3, res);
		}
	};

	TEST_CLASS(P7746)
	{
		//【树状数组 差分数组 DFS序】P7746 [COCI 2011/2012 #3] PLAĆE|普及+
		class Solution {
		public:
			vector<int> Ans(const int N,vector<int>& vInit,vector<int> par,vector<pair<int,int>>& que) {
				for (auto& i : par) { i--; }
				CParentToNeiBo pn(par);
				vector<int> vSort(N), vEnd(N);
				int iSort = 0;
				function<void(int)> DFS = [&](int cur) {
					vSort[cur] = iSort++;
					for (const auto& chi : pn.m_vChild[cur]) {
						DFS(chi);
					}
					vEnd[cur] = iSort;
				};
				DFS(0);
				vector<int> ans;
				CTreeArr<int> bit(N+1);
				for ( auto [x, y] : que) {					
					if (-1 == x) {
						y--;
						ans.emplace_back(bit.Sum(vSort[y]) + vInit[y]);
					}
					else {
						x--;
						bit.Add(vSort[x]+1, y);
						bit.Add(vEnd[x], -y);
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<int> vInit, par;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod11)
		{
			N = 2, vInit = { 5,3 },par = { 0,1 },que = { {1,5},{-1,2},{-1,1} };
			auto res = Solution().Ans(N, vInit, par, que);
			AssertEx({ 8,5 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 5, vInit = { 4,2,6,7,3 },par = { 0,1,1,1,4 },que = { {-1,3},{1,-1},{-1,3},{4,5},{-1,5} };
			auto res = Solution().Ans(N, vInit, par, que);
			AssertEx({ 6,5,7 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 6, vInit = { 5,4,3,7,2,3 },par = { 0,1,2,3,3,5 },que = { {3,2},{2,4},{-1,3},{-1,6},{5,-2},{-1,6},{-1,1} };
			auto res = Solution().Ans(N, vInit, par, que);
			AssertEx({ 7,9,7,5 }, res);
		}
	};

	TEST_CLASS(P12385)
	{
		//【DFS序 异或树状数组 线段树】P12385 [蓝桥杯 2023 省 Python B] 异或和|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector<int>& a, vector<pair<int, int>> edge, vector<tuple<int, int, int>>& ope) {
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				int m_iSort = 0;
				vector<int> vSort(N), vSortEnd(N);
				function<void(int,int)> DFS = [&](int cur, int par) {
					vSort[cur] = m_iSort++;
					for (const auto& next : neiBo[cur]) {
						if (next == par) { continue; }
						DFS(next, cur);
					}
					vSortEnd[cur] = m_iSort;
				};
				DFS(0, -1);
				CTreeArrXor<int> bit(N);
				vector<int> tmp1(N);
				for (int i = 0; i < N; i++) {
					bit.Add(vSort[i], a[i]);
					tmp1[vSort[i]]=bit.Get(vSort[i]);
				}
				
				vector<int> ans;
				for ( auto [kind, x, y] : ope) {
					x--;
					if (1 == kind) {
						const int inx = vSort[x];
						bit.Add(inx, y ^ bit.Get(inx));
						tmp1[inx] = bit.Get(inx);
					}
					else {
						const int cur = bit.Sum(vSortEnd[x] - 1) ^ bit.Sum(vSort[x] - 1);
						ans.emplace_back(cur);
					}
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<pair<int, int>> edge;
		vector<tuple<int, int, int>> ope;
		TEST_METHOD(TestMethod11)
		{
			a = { 1,2,3,4 }, ope = { {2,1,0},{1,1,0},{2,1,0},{2,2,0} }, edge = { {1,2},{1,3},{2,4} };
			auto res = Solution().Ans(a.size(), a, edge, ope);
			AssertEx({ 4,5,6 }, res);
		}
	};

	TEST_CLASS(P10298)
	{
		//【图论 DFS搜索树】P10298 [CCC 2024 S4] Painting Roads|普及+
		class Solution {
		public:
			string Ans(const int N, vector<pair<int,int>>& edge) {
				for (auto& [u, v] : edge) { u--, v--; }
				auto neiBo = CNeiBo::Two(N, edge, false, 0);
				vector<int> pars(N, -1), leves(N,-1);
				function<void(int, int,int)> DFS= [&](int cur, int par,int leve) {
					if (-1 != leves[cur]) { return; }
					leves[cur] = leve;
					pars[cur] = par;
					for (const auto& next : neiBo[cur]) {
						if (next == par) { continue; }
						DFS(next, cur, leve + 1);
					}
				};
				for (int i = 0; i < N; i++) {
					DFS(i, -1, 0);
				}
				string str;
				for ( auto [u, v] : edge) {
					if (leves[u] < leves[v]){ swap(u, v); }
					if (leves[u] != 1 + leves[v]) { str += "G"; continue; }
					str += ((leves[u] & 1)? "B" : "R");
				}
				return str;
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			N = 5, edge = { {1,2},{2,4},{5,2},{4,5},{4,3},{1,3},{1,4} };
			auto res = Solution().Ans(N,edge);
			AssertEx("BRGBBGG", res.c_str());
		}
		TEST_METHOD(TestMethod12)
		{
			N = 4, edge = { {1,2},{3,4} };
			auto res = Solution().Ans(N, edge);
			AssertEx("BB", res.c_str());
		}
	};
	TEST_CLASS(LC3715)
	{//【DFS 数论】3715完全平方数的祖先个数总和|分数未知
		class Solution {
		public:
			long long sumOfAncestors(int n, vector<vector<int>>& edges, vector<int>& nums) {
				for (auto& i : nums) {
					for (int j = 2; j * j <= i;j++) {
						while (0 == i % (j * j)) { i /= (j * j); }
					}
				}
				auto neiBo = CNeiBo::Two(n, edges, false, 0);
				const int M = *max_element(nums.begin(), nums.end());
				vector<int> cnt(M + 1);
				function<void(int, int)> DFS = [&](int cur, int par) {
					m_iAns += cnt[nums[cur]];
					cnt[nums[cur]]++;
					for (const auto& next : neiBo[cur]) {
						if (next == par) { continue; }
						DFS(next, cur);
					}
					cnt[nums[cur]]--;
				};
				DFS(0, -1);
				return m_iAns;
			}
			long long m_iAns = 0;
		};
	public:
		int n;
		vector<vector<int>> edges;
		vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			n = 3, edges = { {0,1},{1,2} }, nums = { 2,8,2 };
			auto res = Solution().sumOfAncestors(n, edges, nums);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 3, edges = { {0,1},{0,2} }, nums = { 1,2,4 };
			auto res = Solution().sumOfAncestors(n, edges, nums);
			AssertEx(1LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 4, edges = { {0,1},{0,2},{1,3} }, nums = { 1,2,9,4 };
			auto res = Solution().sumOfAncestors(n, edges, nums);
			AssertEx(2LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			n = 4, edges = { {0,1},{1,2},{0,3} }, nums = { 175,175,2800,14175 };
			auto res = Solution().sumOfAncestors(n, edges, nums);
			AssertEx(4LL, res);
		}

	};
}


